﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Drawing;
using System.Diagnostics;

namespace LabTask1Sharp
{
    class Graph
    {
        #region MemberData
        public bool HasStartSelected { get; set; }

        public bool HasEndSelected { get; set; }

        private const int CIRCLESIZE = 20;
        private List<Node> nodes = new List<Node>();
        private List<Link> links = new List<Link>(); 
        #endregion

        #region Constructor
        public Graph()
        {
            HasEndSelected = HasStartSelected = false;
        } 
        #endregion

        #region FileIO
        public void ReadNodes(string filename)
        {
            string line;
            try
            {
                StreamReader fin = new StreamReader(filename);
                while ((line = fin.ReadLine()) != null)
                {
                    string[] elements = line.Split(';');
                    if (elements[0].CompareTo("Name") != 0 && elements.Length == 3)
                    {
                        nodes.Add(new Node(elements[0], Convert.ToInt32(elements[1]), Convert.ToInt32(elements[2])));
                    }
                }
            }
            catch (Exception crap)
            {
                System.Windows.Forms.MessageBox.Show(crap.Message);
            }
        }
        public void ReadLinks(string filename)
        {
            string line;
            try
            {
                StreamReader fin = new StreamReader(filename);
                while ((line = fin.ReadLine()) != null)
                {
                    string[] elements = line.Split(';');
                    if (elements[0].CompareTo("from") != 0 && elements.Length == 2)
                    {
                        links.Add(new Link(elements[0], elements[1]));
                    }
                }
            }
            catch (Exception crap)
            {
                System.Windows.Forms.MessageBox.Show(crap.Message);
            }
        } 
        #endregion

        #region Graphics
        public void DrawMap(Graphics g)
        {
            Pen outlinePen = new Pen(Color.Black, 3);
            Pen startPen = new Pen(Color.Green, 3);
            Pen endPen = new Pen(Color.Red, 3);
            Pen pen = new Pen(Color.Blue);
            Font font = new Font(FontFamily.GenericMonospace, 12, FontStyle.Bold);
            Brush brush = new SolidBrush(Color.DarkGray);
            Brush dropBrush = new SolidBrush(Color.Black);
            Brush fontBrush = new SolidBrush(Color.Magenta);
            foreach (var node in nodes)
            {
                g.FillEllipse(brush, node.X - CIRCLESIZE / 2, node.Y - CIRCLESIZE / 2, CIRCLESIZE, CIRCLESIZE);
                g.DrawString(node.Name, font, dropBrush, node.X + 6, node.Y - 21);
                g.DrawString(node.Name, font, fontBrush, node.X + 5, node.Y - 20);

                if (node.IsStart)
                    g.DrawEllipse(startPen, node.X - CIRCLESIZE / 2, node.Y - CIRCLESIZE / 2, CIRCLESIZE, CIRCLESIZE);
                else if (node.IsEnd)
                    g.DrawEllipse(endPen, node.X - CIRCLESIZE / 2, node.Y - CIRCLESIZE / 2, CIRCLESIZE, CIRCLESIZE);
                else
                    g.DrawEllipse(outlinePen, node.X - CIRCLESIZE / 2, node.Y - CIRCLESIZE / 2, CIRCLESIZE, CIRCLESIZE);
            }
            foreach (var link in links)
            {
                Node start = nodes.Find(x => x.Name == link.Start);
                Node end = nodes.Find(x => x.Name == link.End);
                g.DrawLine(pen, start.X, start.Y, end.X, end.Y);
            }
        }

        public void DrawPath(List<Node> path, Graphics g, Color color)
        {
            if (path.Count > 1)
            {
                Pen pen = new Pen(color, 3);
                int fromX = path[0].X;
                int fromY = path[0].Y;
                for (int i = 1; i < path.Count; i++)
                {
                    g.DrawLine(pen, fromX, fromY, path[i].X, path[i].Y);
                    fromX = path[i].X;
                    fromY = path[i].Y;
                }
            }
        }

        public bool CheckIfAnyNodeClicked(int x, int y, System.Windows.Forms.MouseButtons button)
        {
            foreach (var node in nodes)
            {
                if (x < (node.X + 10) && x > (node.X - 10) &&
                    y < (node.Y + 10) && y > (node.Y - 10))
                {
                    if (button == System.Windows.Forms.MouseButtons.Left && !HasStartSelected)
                    {
                        node.IsStart = HasStartSelected = true;
                        if (node.IsEnd)
                            node.IsEnd = HasEndSelected = false;
                    }
                    else if (button == System.Windows.Forms.MouseButtons.Right && !HasEndSelected)
                    {
                        node.IsEnd = HasEndSelected = true;
                        if (node.IsStart)
                            node.IsStart = HasStartSelected = false;
                    }
                    else
                    {
                        if (node.IsEnd)
                            node.IsEnd = HasEndSelected = false;
                        else if(node.IsStart)
                            node.IsStart = HasStartSelected = false;
                    }
                    return true;
                }
            }
            return false;
        } 

        public void ClearExpanded()
        {
            foreach (var node in nodes)
            {
                node.Expanded = false;
            }
        }
        #endregion

        #region Search
        private List<Node> GetChildren(Node node)
        {
            Console.Write(string.Format("{0,-40}","Expanding node " + node.Name + "..."));
            List<Node> children = new List<Node>();
            foreach (var link in links)
            {
                if (link.Start == node.Name)
                {
                    Node childNode = nodes.Find(x => x.Name == link.End);
                    if (!children.Contains(childNode))
                        children.Add(childNode);
                }
                else if (link.End == node.Name)
                {
                    Node childNode = nodes.Find(x => x.Name == link.Start);
                    if (!children.Contains(childNode))
                        children.Add(childNode);
                }
            }
            Console.WriteLine(" " + children.Count + " childnodes found");
            return children;
        }

        #region IterativeDeepening
        public List<Node> IDDFSearch()
        {
            Node start = nodes.Find(x => x.IsStart);
            Node goal = nodes.Find(x => x.IsEnd);
            Console.WriteLine("***********************************************************");
            Console.WriteLine("    Running Iterative Deepening Search on the graph...     ");
            Console.WriteLine("               " + start.Name + " -> " + goal.Name);
            Console.WriteLine("***********************************************************");            
            int expanded = 0;
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Reset();
            stopwatch.Start();

            for (int i = 0; i < 20; i++)
            {
                List<List<Node>> frontier = new List<List<Node>>();
                frontier.Add(new List<Node>() { start });
                while (frontier.Count != 0)
                {
                    List<Node> path = frontier.Last();
                    frontier.Remove(path);
                    if (path.Last().Name == goal.Name)
                    {
                        stopwatch.Stop();
                        Console.WriteLine("-----------------------------------------------------------");
                        Console.WriteLine("Path found to goal after " + stopwatch.ElapsedMilliseconds + "ms");
                        Console.WriteLine(expanded + " node expansions were performed");
                        Console.WriteLine("-----------------------------------------------------------");
                        return path;
                    }
                    if (path.Count < i)
                    {
                        expanded++;
                        path.Last().Expanded = true;
                        foreach (var child in GetChildren(path.Last()))
                        {
                            if (!path.Contains(child))
                            {
                                frontier.Add(new List<Node>(path.Concat(new List<Node>() { child })));
                            }
                        }
                    }
                }
            }
            return null;
        } 
        #endregion

        #region GreedyBestFirst
        public List<Node> GBFSearch()
        {
            Node start = nodes.Find(x => x.IsStart);
            Node goal = nodes.Find(x => x.IsEnd);
            Console.WriteLine("***********************************************************");
            Console.WriteLine("     Running Greedy Best First Search on the graph...      ");
            Console.WriteLine("               " + start.Name + " -> " + goal.Name);
            Console.WriteLine("***********************************************************");
            List<List<Node>> frontier = new List<List<Node>>();
            frontier.Add(new List<Node>() { start });

            int expanded = 0;
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Reset();
            stopwatch.Start();

            while (frontier.Count != 0)
            {
                List<Node> path = GBFSGetBestPath(frontier, goal);
                frontier.Remove(path);
                if (path.Last().Name == goal.Name)
                {
                    stopwatch.Stop();
                    Console.WriteLine("-----------------------------------------------------------");
                    Console.WriteLine("Path found to goal after " + stopwatch.ElapsedMilliseconds + "ms");
                    Console.WriteLine(expanded + " node expansions were performed");
                    Console.WriteLine("-----------------------------------------------------------");
                    return path;
                }
                expanded++;
                path.Last().Expanded = true;
                foreach (var child in GetChildren(path.Last()))
                {
                    if (!path.Contains(child))
                    {
                        frontier.Add(new List<Node>(path.Concat(new List<Node>() { child })));
                    }
                }
            }
            return null;
        }

        private List<Node> GBFSGetBestPath(List<List<Node>> frontier, Node goal)
        {
            List<Node> bestPath = frontier[0];
            double bestPathDist = bestPath.Last().GetDistanceTo(goal);
            for (int i = 0; i < frontier.Count; i++)
            {
                double nextPathDist = frontier[i].Last().GetDistanceTo(goal);
                if (nextPathDist < bestPathDist)
                {
                    bestPath = frontier[i];
                    bestPathDist = nextPathDist;
                }
            }
            return bestPath;
        } 
        #endregion

        #region AStar
        public List<Node> AStarSearch()
        {
            Node start = nodes.Find(x => x.IsStart);
            Node goal = nodes.Find(x => x.IsEnd);
            Console.WriteLine("***********************************************************");
            Console.WriteLine("            Running A* - Search on the graph...            ");
            Console.WriteLine("               " + start.Name + " -> " + goal.Name);
            Console.WriteLine("***********************************************************");
            List<Node> frontier = new List<Node>();
            List<Node> explored = new List<Node>();
            Dictionary<string, Node> parent = new Dictionary<string, Node>();
            Dictionary<string, double> distTraveled = new Dictionary<string, double>();
            frontier.Add(start);
            distTraveled[start.Name] = 0;

            int expanded = 0;
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Reset();
            stopwatch.Start();

            while (frontier.Count != 0)
            {
                Node node = ASSGetBestNode(frontier, distTraveled, goal);
                frontier.Remove(node);
                explored.Add(node);
                if (node.Name == goal.Name)
                {
                    stopwatch.Stop();
                    Console.WriteLine("-----------------------------------------------------------");
                    Console.WriteLine("Path found to goal after " + stopwatch.ElapsedMilliseconds + "ms");
                    Console.WriteLine(expanded + " node expansions were performed");
                    Console.WriteLine("-----------------------------------------------------------");
                    return ASSRebuildPath(start, goal, parent);
                }
                expanded++;
                node.Expanded = true;
                foreach (var child in GetChildren(node))
                {                    
                    double childDist = distTraveled[node.Name] + node.GetDistanceTo(child);
                    if (explored.Contains(child))
                    {
                        if (childDist < distTraveled[child.Name])
                        {
                            frontier.Add(child);
                            explored.Remove(child);
                            distTraveled[child.Name] = childDist;
                            parent[child.Name] = node;
                        }
                    }
                    else if (frontier.Contains(child))
                    {
                        if (childDist < distTraveled[child.Name])
                        {
                            distTraveled[child.Name] = childDist;
                            parent[child.Name] = node;
                        }
                    }
                    else 
                    {
                        frontier.Add(child);                   
                        parent[child.Name] = node;
                        distTraveled[child.Name] = childDist; 
                    }
                }
            }
            return null;
        } 

        private Node ASSGetBestNode(List<Node> frontier, Dictionary<string, double> distTraveled, Node goal)
        {
            Node bestNode = frontier[0];
            double bestNodeDist = distTraveled[bestNode.Name] + bestNode.GetDistanceTo(goal);
            for (int i = 0; i < frontier.Count; i++)
            {
                double nextNodeDist = distTraveled[frontier[i].Name] + frontier[i].GetDistanceTo(goal);
                if (nextNodeDist < bestNodeDist)
                {
                    bestNode = frontier[i];
                    bestNodeDist = nextNodeDist;
                }
            }
            return bestNode;
        }

        private List<Node> ASSRebuildPath(Node start, Node goal, Dictionary<string, Node> parent)
        {
            List<Node> path = new List<Node>();
            Node curNode = goal;
            while (curNode != start)
            {
                path.Add(curNode);
                curNode = parent[curNode.Name];
            }
            path.Add(curNode);
            return path;
        }
        #endregion

        #endregion
    }
}
